/*
 * @lc app=leetcode.cn id=1449 lang=typescript
 *
 * [1449] 数位成本和为目标值的最大数字
 */

// @lc code=start
function largestNumber(cost: number[], target: number): string {
  const dp = new Array(target + 1).fill(Number.NEGATIVE_INFINITY);
  dp[0] = 0;
  for (const c of cost) {
    for (let j = c; j <= target; j++) {
      dp[j] = Math.max(dp[j], dp[j - c] + 1);
    }
  }

  if (dp[target] < 0) return '0';

  let ans = '';
  let i = cost.length;
  let j = target;

  while (i >= 1) {
    let c = cost[i - 1];
    while (j >= c && dp[j] === dp[j - c] + 1) {
      ans += String(i);
      j -= c;
    }
    i--;
  }

  return ans;
}
// @lc code=end
